<?php

/**
 * Created by PhpStorm.
 * User: Administrator
 * Date: 2019/3/2 0002
 * Time: 12:46
 */
//https://blog.csdn.net/u012543061/article/details/52488871
//用PHP实现的单链表
//单链表顾名思义就是一个链式数据结构，它有一个表头，并且除了最后一个节点外，所有节点都有其后继节点
//首先，我们写出链表节点的类。单链表中的每一个节点，都保存其数据域和后驱指针

class node
{
    public $id;//节点id
    public $name; //节点名称
    public $next; //下一个节点

    public function __construct($id, $name, $next = null)
    {
        $this->id = $id;
        $this->name = $name;
        $this->next = $next;
    }
}

//链表中还有两个特别重要的方法，插入和删除。插入需要找到插入的位置，把前一个元素的next指针指向被插入的节点，并将被插入节点的next指针指向
//后一个节点。而删除则是把前一个节点的next指针指向后一个节点，并返回被删除元素的数据内容。
class singleLinkList
{
    private $header; //链表头节点

    public function __construct($id = null, $name = null)
    {
        $this->header = new node($id, $name, null);
    }

    //获取链表的长度
    public function getLinkLength()
    {
        $i = 0;
        $current = $this->header;
        while ($current->next != null) {
            $i++;
            if ($current->next->next == null) break;
            $current = $current->next;
        }
        return $i;
    }

    public function addLink($node)
    {
        $current = $this->header;

        while ($current->next != null) {
            if ($current->next->id > $node->id) break;
            $current = $current->next;
        }
//        var_dump($current);
        //插入需要找到插入的位置，把前一个元素的next指针指向被插入的节点，并将被插入节点的next指针指向后一个节点
        $node->next = $current->next;
        $current->next = $node;

    }

//而删除则是把前一个节点的next指针指向后一个节点，并返回被删除元素的数据内容
    public function delLink($id)
    {
        $current = $this->header;
        $flog = false;
        $del = null;
        while ($current->next != null) {
            if ($current->next->id == $id) {
                $del = $current->next;
                $flog = true;
                break;
            }
            $current = $current->next;
        }

        if ($flog) {
            $current->next = $current->next->next;
        } else {
            echo "未找到id=" . $id . "的节点！<br>";
        }
        return $del;
    }

    public function isEmpty()
    {
        return $this->header == null;
    }

    public function clear()
    {
        $this->header = null;
    }

//获取链表
    public function getLinkList()
    {
        $current = $this->header;
        if ($current->next == null) {
            echo '链表为空';
            return;
        }
        while ($current->next != null) {
            echo 'id:' . $current->next->id . '   name:' . $current->next->name . "\r\n";
            if ($current->next->next == null) break;
            $current = $current->next;
        }
    }

//获取节点名字
    public function getLinkNameById($id)
    {
        $current = $this->header;
        if ($current->next == null) {
            echo '链表为空';
            return;
        }
        while ($current->next != null) {
            if ($current->id == $id) break;
            $current = $current->next;
        }
        return $current->name;
    }

//更新节点名称
    public function updateLink($id, $name)
    {
        $current = $this->header;
        if ($current->next == null) {
            echo '链表为空';
            return;
        }
        while ($current->next != null) {
            if ($current->id == $id) break;
            $current = $current->next;
        }
        return $current->name = $name;
    }

}

$lists = new singleLinkList ();
$lists->addLink(new node (5, 'eeeeee'));
$lists->addLink(new node (4, 'aaaaaa'));
$lists->addLink(new node (3, 'bbbbbb'));
//$lists->addLink(new node (2, 'cccccc'));
//var_dump($lists->delLink(4));
//echo $lists->getLinkLength();
//$lists->getLinkList();
//$lists->getLinkNameById(3);
$lists->updateLink(5,'ccc');
var_dump($lists);
